//
// Created by Administrator on 2021/6/21.
//
#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        /**
         * 储存0-59 每个数中1的位数
         */
        vector<vector<int>> bitCount(10, vector<int>());
        for (int i = 0; i < 60; ++i) {
            int bitNum = __builtin_popcount(i);
            bitCount[bitNum].push_back(i);
        }
        vector<string> ans;
        for (int hour = 0; hour <= turnedOn; ++hour) {
            // 给小时和分针分配灯数
            int minute = turnedOn - hour;
            for (auto &x:bitCount[hour]) {
                if (x >= 12) continue;
                string hourStr = to_string(x);
                for (auto &y:bitCount[minute]) {
                    string minuteStr;
                    minuteStr = y < 10 ? "0" + to_string(y) : to_string(y);
                    ans.push_back(hourStr + ":" + minuteStr);
                }
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution2 sol;
    auto ans = sol.readBinaryWatch(2);
    for (auto &x:ans) cout << x << endl;
    return 0;
}